Intro to Crypto 2 - localo

Category: Crypto
Difficulty: Baby
Author: black-simon

Description

This is an introductory challenge for beginners which want to dive into the world of Cryptography. The three stages of this challenge will increase in difficulty.

I learned my lesson from the mistakes made in the last challenge! Now p and q are huge, I promise!

Summery

The author provided a message.txt and a pubkey.pem
The message.txt contains just a number and the pubkey.pem is a public key. All we have to do is to decrypt the message.txt.

Solution

We need to factor N. Factordb has not factored it. From the description I expected, that they have roughly the same length and used Fermat's factorization method Wikipedia

import OpenSSL.crypto as crypto
from factordb.factordb import FactorDB

key = open("pubkey.pem","rb").read()
message = open("message.txt","rb").read()

key = crypto.load_publickey(crypto.FILETYPE_PEM, key)
numbers = key.to_cryptography_key().public_numbers()

N = numbers.n
E = numbers.e

C = int(message)
def fermat(n):
    a = isqrt(n)
    while True:
        b = a**2-n
        if b > 0 and b.is_square():
            p = int(str(a-isqrt(b)))
            return p,n/p
        a +=1
    
factors = fermat(N)
P = factors[0]
Q = factors[1]
D = xgcd(E,(P - 1) * (Q - 1))[1]
M = pow(C,D,N)
print(hex(int(str(M))).replace("L","")[2:].decode('hex'))

Mitigation

• never roll your own crypto
• use large primes of different length

Flag

CSCG{Ok,_next_time_I_choose_p_and_q_random...}